// 2025/3/22
// https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked
// 每日温度

class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            int n = temperatures.size();
            vector<int> ans(n, 0);
            for(int end = n - 2; end >= 0; end--)
            {
                int cur = end + 1;
                while(ans[end] == 0 && cur < n)
                {
                    if(temperatures[cur] > temperatures[end])
                        ans[end] = cur - end;
                    else if(ans[cur] != 0)
                        cur += ans[cur];
                    else
                        break;
                }
            }
            return ans;
        }
    };

// 单调栈
class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            int n = temperatures.size();
            vector<int> ans(n, 0);
            stack<int> st;
            for(int i = 0; i < n; i++)
            {
                while(!st.empty() && temperatures[i] > temperatures[st.top()])
                {
                    ans[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
            return ans;
        }
    };